package DataStructure.LinkedLearning.SingleLinkedList.ReverseLinked;

/**
 *  学习 反转链表 --- 头插法
 */
public class Demo {
    public static void main(String[] args) {
        Node node1 = new Node("1", null);
        Node node2 = new Node("2", node1);
        Node node3 = new Node("3", node2);
        Node node4 = new Node("4", node3);
        Node node5 = new Node("5", node4);
        Node node6 = new Node("6", node5);
        Node node7 = new Node("7", node6);

        // 7   6  5  4  3  2  1
        // 1   2  3  4  5  6  7


        Node reLinked = reLinked(node7);
        System.out.println(reLinked);

    }

    private static Node reLinked(Node node7) {
        Node reLinked = null ;

        // mid 遍历结点
        Node mid = node7;
        // 遍历结点的下一个结点不为空
        while (mid.next != null){

            // 记录遍历结点的下一个结点, (保存正序序列, 以免丢失)
            Node linkedNext = mid.next;

            // 遍历的结点采用'头插法', 插入反序链表
            mid.next = reLinked;
            // 反序链表的头结点前移
            reLinked = mid;
            // mid指向正序链表
            mid = linkedNext;
        }

        // 处理最后一个正序结点
        mid.next = reLinked;
        reLinked = mid;

        return reLinked;
    }
}
